package 算法.leetcode.offer.nk;

/**
 * @author lchenglong
 * @date 2022/3/26
 */
public class BM20 {

    public static void main(String[] args) {
        int[] array =new int[]{1,2,3,4,5,6,7,0};
        BM20 instance = new BM20();
        int ans = instance.InversePairs(array);
        System.out.println(ans);
    }
    int total = 0;
    int[] array;
    public int InversePairs(int[] array) {
        this.array = array;
        mergeSort(0,array.length-1);
        return total%1000000007;
    }

     void mergeSort(int l,int r){
        if(l>=r)return ;
        // 中间位置
        int mid = (r+l)/2;
        // 递归拆分合并
        mergeSort(l,mid);
        mergeSort(mid+1,r);
        // 最后合并
        merge(l,mid,r);
    }

    void merge(int l,int mid,int r){
        System.out.println( "" + l+"-" + mid+"-"+r);
        // 合并后存放的数组
        int[] tmp = new int[r-l+1];
        int i=l,j=mid+1,k=0;
        while (i<=mid&&j<=r){
            if(array[i]>array[j]){
                tmp[k++] = array[j++];
                total += mid-i+1;
            } else {
                tmp[k++] = array[i++];
            }
        }
        while(i<=mid)tmp[k++] = array[i++];
        while (j<=r)tmp[k++] = array[j++];
        for (k=0,i=l;i<=r;i++,k++)array[i]= tmp[k];
    }
}
